package org.xingole.leetcode.dp;

import java.util.Arrays;

/**
 * <a href="https://leetcode.com/problems/2-keys-keyboard/description/">
 * Problem Description
 * </a>
 * 
 * <p>
 * There is only one character 'A' on the screen of a notepad. You can
 * perform one of two operations on this notepad for each step:
 * 
 * <ul>
 *      <it>Copy All: You can all the characters present on the screen (a partial copy is not allowed).
 *      <it>Paste: You can paste the characters which are copied last time.
 * </ul>
 * 
 */
public class TwoKeysKeyboard {
    private static final int INFINITE = 10001;

    public int minSteps0(int n) {
        // 1. Define Subproblem
        //    Let K(i, j) represent the minimum number of operations to get character 'A' 
        // exactly i times on the screen with j cached 'A's.
        int[][] dp = new int[n + 1][n + 1];

        // 2. Relate the recurrence
        //    a. If i > j, We can choose directly paste from K(i - j, j) to get K(i, j) 
        //    b. If i = j, alternative way to copy all characters K(i, k) for 0 <= k <= i
        //    c. If i < j, the cases will not happen denote positive infinite
        //           |-> K(i-j, j) + 1,                          if i > j
        // K(i, j) = |-> min(K(i, k)) + 1, for all 0 <= k < i    if i = j    
        //           |-> positive infinite                       otherwise
        // for all cases, i > 0, j >= 0

        // base case
        dp[1][0] = 0; dp[1][1] = 1;
        for(int j = 2; j < n + 1; j++)
            dp[1][j] = INFINITE;
        for(int i = 2; i < n + 1; i++)
            dp[i][0] = INFINITE;

        for(int i = 2; i < n + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                if(i < j)  
                    dp[i][j] = INFINITE;
                else if(i > j) {
                    dp[i][j] = dp[i - j][j] + 1;
                } else {
                    dp[i][j] = INFINITE;
                    for(int k = 0; k < i; k++) {
                        dp[i][j] = Math.min(dp[i][k], dp[i][j]);
                    }
                    dp[i][j] += 1;
                }

                if(dp[i][j] > INFINITE)
                    dp[i][j] = INFINITE;
            }
        }

        // int r = 0;
        // for(int[] d : dp) {
        //     System.out.print("Times " + (r++) + ": ");
        //     for(int j : d) {
        //         System.out.print(j + " ");
        //     }
        //     System.out.println();
        // }

        int min = INFINITE;
        for(int j = 0; j < n + 1; j++) {
            min = Math.min(dp[n][j], min);
        }

        return min;
    }

    /**
     * Approach 1: Recursion 
     * 
     * Intuition
     *
     * When adding A's on the screen to achieve n A's, we note that it is unnecessary to apply
     * consecutive Copy All operations has the same effect as applying just one. If a Conpy All
     * operation is applied, the a Paste operation should be applied right after. Thus, we have
     * two options to add A's on the screen at every step:
     *
     * 1. Apply a Copy All operation first and then apply the Paste operation right after.
     * 2. Apply a Paste operation.
     *
     * A brute-force approach involves exploring both ways recursively at each step. This would allow 
     * us to find all possible sequences of operations result in exactly n A's, and then choose the
     * sequence that requires the minimum number of operations.
     *
     * To implement this, we define a function f(i, j), which represents the minimum number of operations
     * needed to get to n A's starting with i A's, where the previous copy operation has j A's.
     *
     * We can break the problem into subproblems based on the two options described above:
     * 
     * 1. Copy All + Paste: This option takes 2 operations. It doubles the number of A's to i*2, and updates
     * the previous copy length to i. Thus, the number of operations needed for this choice is 2 + f(i * 2, i).
     *
     * 2. Paste: This option takes 1 Paste operation. It increases the number of A's by j while keeping 
     * keeping the previous copy length as j. Thus, the number of operations needed for this choice is 
     * 1 + f(i + j, j).
     *
     * By making recusive calls for these two choices - 2 + f(i * 2, i) and 1 + f(i + j, j) = our solution
     * can return the minimum value among these options, effectively finding the global minimum number of 
     * operations needed to reach n A's */
    private int n;
    public int minSteps1(int n) {
        if(n == 1) return 0;
        this.n = n;
        // first step is always a Copy All operation
        return 1 + minStepsHelper(1, 1);
    }

    private int minStepsHelper(int currLen, int pasteLen) {
        // base case: reached n A's, don't need more operations
        if(currLen == n) return 0;

        // base case: exceed n 'A''s, not a valid sequence, so
        // return max value
        if(currLen > n) return 1000;

        // Copy all + paste
        int opt1 = 2 + minStepsHelper(currLen * 2, currLen);
        
        // paste
        int opt2 = 1 + minStepsHelper(currLen + pasteLen, pasteLen);

        return Math.min(opt1, opt2);
    }
    /**
     * 
     * @param n a given integer
     * @return the minimum number of operations to get the character 'A' exactly n times on
     * the screen.
     */
    public int minSteps2(int n) {
        /**
         * Let dp[i] represent the minimum number of operations required to print out i As.
         */
        int[] dp = new int[n + 1];

        // base case
        dp[1] = 0;

        // Since we can only use the two operations of "copy all" and "paste", to obtain i As, we
        // must first have j As, then use the "Copy All" operation once, and the then use serval
        // "paste" operations to get i As.
        // We can enumerate j for state transition and in this way we obtain the state transition
        // equation: dp[i] = min{ dp[jj] + i / j } for all j the factors of i
        for (int i = 2; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; ++j) {
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                    dp[i] = Math.min(dp[i], dp[i / j] + j);
                }
            }
        }

        return dp[n];
    }
    /** 
     * Approach 3: Bottom-Up Dynamic Programming
     *
     * Intuition
     *
     * An alternate approach is to solve our subproblems from bottom to top, by working from the base
     * case up to the final answer.
     *
     * We define a new function f(i) to represent the minimum number of operations to get to i A's 
     * starting from 1 A. Note that in contrast to Apporaches 1 and 2, we do not keep track of the 
     * length of the previous copy. This approach focuses on incrementally building up from the base
     * case f(1) = 0 to f(n), the final result.
     *
     * To do this, we'd like to form a relation between subproblems and express f(i) in terms of f(j) 
     * for values of j where 1 <= j < i. 
     *
     * For a given subproblem f(i) where there are currenlty i A's, we recognize the last operation must
     * have been a paste. Furthemore, we know that the number of A's previously copied must be a factor 
     * of i. 
     *
     * Thus, one possible way to make i A's is to use the Copy All operation on j A's, where j is a factor
     * of i. We can then paste the j A's (i - j)/j times to reach a total of i A's. If this approach is chosen
     * then the minimum number of operations possible would be f(j) + 1 + (i - j)/j. Here, f(j) represents the
     * minimum number of operations to reach j A's, 1 accounts for the single Copy All operations on the j A's, 
     * and (i - j) / j represents the number of additional Paste operations of j A's needed.
     *
     * We can simplify the expression f(j) + 1 + (i - j) / j to f(j) + i / j.
     *
     * If we consider all possible factors j of i, then we can solve for f(j). Thus, we have the relation:
     *
     * f(i) = f(j) + i/j for all j such that i mod j == 0. Note that j <= i/2 since i/2 is the largest 
     * factor of i.
     *
     */
    public int minSteps(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1000);

        // Base case
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                // Copy All and Paste (i-j) / j times
                // for all valid j's
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                }
            }
        }

        return dp[n];
    }
}
